##二叉树
每个节点最多有两个子节点
##二叉查找树
左节点小于父节点，父节点小于右节点
时间复杂度：logN <= O(h) <= N
##自平衡二叉查找树
AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。通过旋转维持平衡，降低时间复杂度。
###旋转轴节点
想要确定旋转轴节点需要先知道几个概念。
- 平衡因子：二叉树某节点左右子树高度差(左减右为正还是右减左为正可自定义，下面的例子假定左减右为正)
- 最小不平衡子树：以距离插入节点最近的且平衡因子绝对值大于1的节点为根节点的子树
- next larger：是指比某个node A 大的值，但是比所有其他大于node A的nodes 都要小；比较绕口，其实本质就是在所有比node A 大的集合中，key值最接近node A 的哪一个node
- next smaller：同理next larger
旋转轴节点的确定，是由最小不平衡子树的平衡因子的正负，来决定找最小不平衡子树根节点的next smaller或者next larger。如果最小不平衡子树的平衡因子为正，其旋转轴节点为其root节点的next smaller；反之同理。 并且旋转轴节点是新子树的根节点。
可以试着用上面的方法确定以下二叉树的旋转轴节点：
###旋转
旋转的目的是，通过降低左右子树的高度，来达到平衡。
首先我们需要知道，我们的旋转对象，或者说平衡目标，是什么？大家可能都知道了，上面我们已经多次提到了，就是最小不平衡子树。
因为自平衡二叉树查找树每一次插入新节点后，都要检查是否破坏了平衡，如果破坏了平衡都会通过旋转来保持平衡。所以说每一次的不平衡状态的平衡因子都只可能为-1或者1，也就是说我们只要解决了最小不平衡子树的不平衡，将其挂在其原有根节点的位置，也就是解决了整棵树的不平衡。
旋转分为两类，单旋转和双旋转。
- 单旋转
当最小不平衡子树的平衡因子与其子树(新加节点路径上的子树)的平衡因子为同符号性质(同为正/负号)时单旋转。
如果不存在左孩子，左旋转会将父节点挂在旋转轴的左孩子处；如果存在左孩子，则需要和做孩子对比大小，如果比其左孩子小的话，就挂在其左孩子的左节点，如果比其左孩子大的话，就替换为其孩子的位置，原来的左孩子挂在新的做孩子的左节点。右旋转的操作同理。 - 双旋转
当最小不平衡子树的平衡因子与其子树(新加节点路径上的子树)的平衡因子为异符号性质(正负/负正)时双旋转。
双旋转就是需要旋转两次，LR或者RL。
以下是一个双旋转RL的过程：
